package club.xiaojiawei.binarytree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/18/22 7:22 PM
 * @question 501. 二叉搜索树中的众数
 * @description 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 * 假定 BST 满足如下定义：
 * 结点左子树中所含节点的值 小于等于 当前节点的值
 * 结点右子树中所含节点的值 大于等于 当前节点的值
 * 左子树和右子树都是二叉搜索树
 */
@SuppressWarnings("all")
public class FindMode501 {

    public static void main(String[] args) {
        FindMode501 test = new FindMode501();
        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(2), null));
        int[] result = test.findMode(root);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 中序遍历
     * @param root
     * @return
     */
    public int[] findMode(TreeNode root) {
        recursion(root);
        int[] result;
        if (preValue[1] == maxCount){
            result = new int[stack.size() - startIndex + 1];
            for (int i = startIndex; i < stack.size(); i++){
                result[i - startIndex] = stack.get(i)[0];
            }
            result[stack.size() - startIndex] = preValue[0];
        }else if (preValue[1] > maxCount){
            result = new int[]{preValue[0]};
        }else {
            result = new int[stack.size() - startIndex];
            for (int i = startIndex; i < stack.size(); i++){
                result[i - startIndex] = stack.get(i)[0];
            }
        }
        return result;
    }

    ArrayList<int[]> stack = new ArrayList<>();

    int maxCount = 0;

    int[] preValue = null;

    int startIndex = 0;

    public void recursion(TreeNode node){
        if (node == null){
            return;
        }
        recursion(node.left);
        if (preValue == null){
            preValue = new int[]{node.val, 1};
        }else if (node.val == preValue[0]){
            preValue[1]++;
        }else {
            if (preValue[1] == maxCount){
                stack.add(preValue);
            }else if (preValue[1] > maxCount){
                stack.add(preValue);
                maxCount = preValue[1];
                startIndex = stack.size() - 1;
            }
            preValue = new int[]{node.val, 1};
        }
        recursion(node.right);
    }

    List<Integer> answer = new ArrayList<Integer>();
    int base, count, maxCount2;

    /**
     * 官方-中序遍历
     * @param root
     * @return
     */
    public int[] findMode2(TreeNode root) {
        dfs(root);
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }

    public void dfs(TreeNode o) {
        if (o == null) {
            return;
        }
        dfs(o.left);
        update(o.val);
        dfs(o.right);
    }

    public void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount2) {
            answer.add(base);
        }
        if (count > maxCount2) {
            maxCount2 = count;
            answer.clear();
            answer.add(base);
        }
    }

    /**
     * Morris 中序遍历
     * @param root
     * @return
     */
    public int[] findMode3(TreeNode root) {
        TreeNode cur = root, pre = null;
        while (cur != null) {
            if (cur.left == null) {
                update2(cur.val);
                cur = cur.right;
                continue;
            }
            pre = cur.left;
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            } else {
                pre.right = null;
                update2(cur.val);
                cur = cur.right;
            }
        }
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }

    public void update2(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.add(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
